Multi-Armed Bandit

问题描述 #card

• 多臂老虎机是一种赌博机器，每台老虎机有若干手柄，拉动其中一根手柄，老虎机将会吐出一些金币。

• 每根手柄每次吐出的金币数是随机的，但是遵循一个固定但对赌徒未知的概率分布。

• 赌徒一共有N次机会，他希望找到一个最优策略使他能获得的金币数最多。

朴素解法

• 将 N 次划分成 [[exploration and exploitation]] 两个阶段 #card

  • 先探索，也就是将每根手柄拉动 $n$ 次，统计 $\bar{R}(i)$ 为拉动第 1 根手柄 $n$ 次所得到的平均收益。

  • 再开发，赌徒找到平均收益最大的那根手柄 $a_{\max }=\operatorname{argmax}i \bar{R}(i)$ ，然后将剩余的机会全部用来拉动 $a{\text {max }}$ 。

• 朴素Bandit算法的缺点在于前期探索的次数很难设置 #card

  • 如果前期每个手柄探索的次数太少，统计出来的每根手柄的平均收益 $\bar{R}$ 误差大，导致探索出来的最优手柄的置信度太低，后期开发阶段可能陷入某个次优方案而不自知。

  • 如果前期每根手柄探索的次数太多，每根手柄的平均收益 $\bar{R}$ 会准确些，探索出来的最优手柄的置信度会高些，但此时留给＂开发＂的拉动机会就不多了。

Epsilon Greedy

• 将探索与开发按照一定概率交替进行，在找到当前最优手柄的同时就充分加以开发利用，以最大化总收益。#card
  

Decay Epsilon Greedy

• 让决定是否探索的门槛值 $\epsilon$ 随时间衰减。#card

  • 前期 $\epsilon$ 较大，算法有更多的机会去探索各手柄的收益。

  • 随着尝试次数变多，统计出来的 $\bar{R}$ 更加准确，找到的最优手柄 $a_{\text {max }}$ 的置信度更高。

    • 此时 $\epsilon$ 也变小了，鼓励算法充分利用 $a_{\text {max }}$ 赚取最大收益，而非浪费机会在不必要的探索上。